<head>
    <meta charset="UTF-8">
<title>算法训练 Collecting Luggage</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">航班结束后，提取行李的过程并不琐碎。手提箱和行李箱出现在一条传送带上，数百名乘客争夺有利的位置从中找到并取回自己的所有物。近日，成田机场管理局已决定使这一过程更加高效。在重新设计行李认领区前，他们需要一个模拟程序，使得乘客认领行李时的耗时更平均。这个模拟假定乘客们走一条由直线段组成的路径并使用最少的时间走到他们的行李处。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">对于这个问题，传送带被描述为一个简单多边形。在传送带的某些点上出现一件行李，然后以恒定的速度沿着传送带移动。乘客一开始在一个传送带组成的多边形外的点。在行李出现的同时，乘客以恒定的速度（大于行李移动的速度）移动去提取行李。乘客的路径可以接触但不能穿过传送带，且能让乘客在最短的时间内和行李位于同一个点。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">在接下来这幅图中，传送带被描述成多边形</span><span lang="EN-US">ABCDEF</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。行李开始在左上角（</span><span lang="EN-US">A</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">点）并按时针方向沿多边形边缘移动，如小箭头所示。乘客一开始在</span><span lang="EN-US">P</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">点，并开始按最短的时间能和行李到达同一点（图中</span><span lang="EN-US">M</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">点）的路径移动。乘客的移动路径如红色箭头所示。该图对应第一个输入样例。</span></p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=M9YYHM3r" width="738" height="284" alt="" /></p>
<p>【输入格式】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">输入包含一个或多个测试点来描述领取行李的场景。一个场景描述开头一行为一个单独的整数</span><span lang="EN-US">N(3&lt;=N&lt;=100)</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">，多边形的顶点数。接下来</span><span lang="EN-US">N</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">行每行两个整数</span><span lang="EN-US">x<sub>i</sub>,y<sub>i</sub>,(|x<sub>i</sub>|,|y<sub>i</sub>|&lt;=10000)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，按逆时针顺序给出多边形顶点的坐标。多边形是简单多边形，也就是说它不自交，不重合。多边形的描述后接下来一行两个整数</span><span lang="EN-US">p<sub>x</sub>,p<sub>y</sub>(|p<sub>x</sub>|,|p<sub>y</sub>|&lt;=10000)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，乘客起始位置所在点的坐标。接下来两个正整数</span><span lang="EN-US">V<sub>L</sub>,V<sub>P</sub>(0&lt;V<sub>L</sub>&lt;V<sub>P</sub>&lt;=10000)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，分别是行李和乘客的速度。所有坐标的单位是米，速度的单位是米</span><span lang="EN-US">/</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">分钟。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">你可以假设乘客位于多边形外。行李将会从多变形的第一个顶点开始按逆时针顺序沿传送带移动。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">输入以一行一个单独的</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">结束。</span></p>
<p>【输出格式】</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp; &nbsp; &nbsp; &nbsp;</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">对于每组数据，输出一行，包括测试数据编号（从</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">开始编号）和乘客取得行李的最少时间。使用格式如样例输出所示（用冒号隔开分钟和秒），四舍五入到最近的整数。秒数占两位（不足用前导</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">补齐）。</span></p>
<p>【样例输入】</p>
<p>6&nbsp;</p>
<p>0 40&nbsp;</p>
<p>0 0&nbsp;</p>
<p>20 0&nbsp;</p>
<p>20 20&nbsp;</p>
<p>40 20&nbsp;</p>
<p>40 40&nbsp;</p>
<p>120 40&nbsp;</p>
<p>70 100&nbsp;</p>
<p>4</p>
<p>0 0&nbsp;</p>
<p>10 0&nbsp;</p>
<p>10 10&nbsp;</p>
<p>0 10&nbsp;</p>
<p>100 100&nbsp;</p>
<p>10 11&nbsp;</p>
<p>0</p>
<p>【样例输出】</p>
<p>Case 1: Time = 1:02</p>
<p>Case 2: Time = 12:36</p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span>【数据规模和约定】</p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">对于</span><span lang="EN-US">10%</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的数据，给出的多边形保证是凸多边形</span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">对于</span><span lang="EN-US">20%</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的数据，</span><span lang="EN-US">3&lt;=n&lt;=4</span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">对于</span><span lang="EN-US">40%</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的数据，</span><span lang="EN-US">3&lt;=n&lt;=50</span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">对于</span><span lang="EN-US">100%</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的数据，</span><span lang="EN-US">3&lt;=n&lt;=100</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，数组组数</span><span lang="EN-US">&lt;=10</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，坐标绝对值、速度</span><span lang="EN-US">&lt;=10000</span></p>